package offer.offer03;

/**
 *
 */
public class S47礼物的最大值 {
    /**
     * 81, 动态规划, 把找max从n2循环移出去在边界判断时间减少了一半。
     * 首先肯定是每个点都要被看到的, 所以最小时间复杂度就是n2了。
     * 只能向右或者向下, 表示如果顺序遍历, 那么是不用回退的。
     */
    public int maxValue(int[][] grid) {
        // int max = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                // 我傻了, 一维[i, j]是java二维的索引, 其实是[i][j]
                grid[i][j] = Math.max((i == 0? 0: grid[i - 1][j]) + grid[i][j],
                        (j == 0? 0: grid[i][j - 1]) + grid[i][j]);
                // max = Math.max(max, grid[i][j]);
            }
        }
        int max = 0;
        int len = grid[0].length - 1;
        for(int i = 0; i < grid.length; i++){
            max = Math.max(max, grid[i][len]);
        }
        len = grid.length - 1;
        for(int i = 0; i < grid[0].length; i++){
            max = Math.max(max, grid[len][i]);
        }
        return max;
    }
}
